package com.practice.sequence;

import java.util.Stack;

/**
 * Given an array of integer, find the largest rectangle in histogram.
 */
public class LargestRectangleInHistogram {
	public int maxRectangle(int[] a) {
		int max = 0;
		Stack<Node> s = new Stack<Node>();
		
		for (int i=0; i<a.length; i++) {
			Node node = new Node(i, a[i]);
			if (s.isEmpty()) {
				s.push(node);
				continue;
			}
			
			Node top = s.peek();
			if (top.value < a[i]) {
				s.push(node);
			}
			else if (top.value > a[i]) {
				while (!s.isEmpty() && s.peek().value>=a[i]) {
					Node prev = s.pop();
					node.x = prev.x;
					if (prev.value*(i-prev.x) > max) max = prev.value*(i-prev.x);
				}
				s.push(node);
			}
		}
		
		while (!s.isEmpty()) {
			Node n = s.pop();
			if ((a.length-n.x)*n.value > max) max = (a.length-n.x)*n.value;
		}
		
		return max;
	}
	
	private class Node {
		int	x;
		int value;
		
		public Node(int x, int value) {
			this.x = x;
			this.value = value;
		}
	}
}
